package leetcode.day_2021_03_8_2021_03_14;

import javax.jnlp.ClipboardService;
import java.util.ArrayList;
import java.util.List;

/**
 * 60. 排列序列
 * https://leetcode-cn.com/problems/permutation-sequence/
 */
public class LeetCode0060 {

    public static String getPermutation(int n, int k) {
        // 定义数组
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = i+1;
        }
        boolean[] used = new boolean[n];
        List<String> list = new ArrayList<String>();
        backtrack(arr, n, used, k, new StringBuilder(), list);
        return list.get(k-1);
    }

    public static void backtrack(int[] nums, int n, boolean[] used, int k, StringBuilder str, List<String> list) {
        if (str.length() == nums.length) {
            list.add(str.toString());
            return;
        }

        for (int i=0; i<n; i++) {
            if (list.size() == k) {
                break;
            }
            if (used[i]) continue;
            str.append(nums[i]);
            used[i] = true;
            backtrack(nums, n, used, k, str, list);
            str.deleteCharAt(str.length()-1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 3));
        System.out.println(getPermutation(4, 9));
        System.out.println(getPermutation(3, 1));
        System.out.println(getPermutation(9, 296662));
        System.out.println(getPermutation(9, 25996));
    }
}
